#include <stdio.h>
typedef int Elemtype

void quickSort(Elemtype *a, int p, int r)
{
	if (p < r)
	{
		int q = partition(a,p,r);
		quickSort(a, p, j);
		quickSort(a, j+1, r);
	}
}

int partition(Elemtype *a, int p, int r)
{
	int i = p, j = r + 1;
	Elemtype x = a[p];

	while (1)
	{
		while (a[++i] < x && i < r);
		while (a[--j] > x);

		if (i >= j)
			break;

		Elemtype tmp;
		tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	a[p] = a[j];
	a[j] = x;

	return j;
}